The present invention relates to a network designing method and to a recording medium on which the control program is recorded. Particularly, the present invention is to provide a method of designing an inter-ring connection network with a fault-recoverable feature.
Ring systems have been used in order to secure communications by quickly using an alternate line when a failure occurs in a communication system (refer to, Tsong-Ho wu, Fiber Network Survivability, 1992, Artech House). FIG. 10 illustrates the topology of a communication network where the ring systems can be installed. The topology consists of nodes 1 and spans 2. A ring system is formed by the ring 3. The ring 3 represents a closed path which does not contain the same nodes 1 of two or more and the same nodes 2 of two or more.
As shown in FIGS. 11 and 13, the ring system consists of an add drop multiplexers (ADMS) 61 to 64 and fibers 7 and 71 to 74. The ADM 61 is set up to the node 1 configuring the ring 3. The fiber 71 is set up to the span 3 configuring the ring 3. Plural ring systems may be set up to the same ring 3.
The ADM 6, as shown in FIG. 12, separates the channel 103 to be received from the fiber 75 or inserts the channel 104 to be transmitted in the fiber 76. Specifically, the channel 101 with the slot #1 allocated and the channel 102 with the slot #2 allocated can pass through the ADM 6 while the slot numbers are not changed. The channel 103 with the slot #3 allocated is branched from the fiber 75 to receive by the ADM 6. The channel 104 with the slot #4 allocated is inserted in the fiber 76 to transmit from the ADM 6. The slot represents identifying channels multiplexed within a single fiber. Specifically the time slot in time division multiplex corresponds to the wavelength in wave division multiplex.
As disclosed in the foregoing literature, the ring system is roughly classified into a bi-directional ring system and an uni-directional ring system. FIG. 11 illustrates the configuration of the bi-directional ring system 8. Referring to FIG. 11A, a group of working fibers are set up in the bi-directional ring system 8 to accommodate bi-directional channels between certain ADMs in a normal state.
For example, the channels 106 and 107 are bi-directionally installed along the path routing counterclockwise from the ADM 61 to the ADM 64. Moreover, a group of spare fibers that can accommodate bi-directional channels are installed for the failure. At a system failure, the ADMs connected to both ends of the spare fiber group changes the fiber connection. As shown in FIG. 11B, when the working fiber 71 and the spare fiber 72 between the ADMs 62 and 63 are cut, the ADM 62 is connected to the spare fiber 73 while ADM 63 is connected to the spare fiber 74. Thus, the channel 106 is changed to the channel 108 so that the channel routing from the ADM 64 to the ADM 61 is secured.
FIG. 13 shows slot numbers allocated to respective channels on the uni-directional fiber set between ADMs in the bidirectional ring system 8. In this example, it is assumed that 32 channels per fiber at maximum can be multiplexed. Each ADM, as shown in FIG. 11, does not change the slot number of the channel 10 passing through the ADM. Hence, the same slot number must be allocated to the fiber through which each channel 10 is routed.
Referring to FIG. 13, 8 channels are set between the ADMs 61 and 63. Slot numbers #12 to #19 are respectively allocated to the 8 channels along the path routing clockwise or counterclockwise between the ADM 61 and the ADM 63. The channel with #20 allocated is set along the path routed counterclockwise between the ADMs 63 and 64. The channels with the slot numbers #1 to #7 are set along the path routing clockwise between the ADMs 61 and 64. The channels with the slot numbers #1 to #11 are set along the path routing counterclockwise between the ADMs 61 and 64.
FIG. 13 shows the method wherein the bi-directional ring system 8 detours around a failure in span units. In addition, there is the failure detouring method which changes channels used across each node pair from channels on a clockwise or counterclockwise routing path to the channels with the same slot on a counterclockwise or clockwise routing path.
In the bi-directional ring system shown in FIG. 11, if the ADM 62 is failed, each of the ADMs 61 and 63 turns back the channels within the working fiber to a spare fiber, so that the failed channel can be restored.
FIG. 14 illustrates the configuration of the unidirectional ring system. As shown in FIG. 14A, the unidirectional ring system 9 simultaneously accommodates in a normal state a group of bidirectional channels in the clockwise direction and a group of bi-directional channels in the counterclockwise direction, which are installed between a group of ADMs 6. For example, the bi-directional channels 109 and 1011 routing between the ADMs 61 and 64 are accommodated clockwise within the uni-directional working fiber 77. Another group of bi-directional channels 1010 and 1012 arc accommodated counterclockwise within the spare fiber 78. The ADM 61 receives two channels 109 and 1010 while the ADM 64 receives two channels 1011 and 1012. As shown in FIG. 14B, cutting the working fiber 77 and the spare fiber 78 between the ADMs 62 and 63 does not adversely affect the channels 1010 and 1011 so that the bi-directional channel between the ADMs 61 and 64 can be secured.
The uni-directional ring system 9 shown in FIG. 14 can secure the bi-directional channels even in a failure of the ADM 62. Unlike the bi-directional ring system 8, the uni-directional system accommodates the bi-directional channels installed between arbitrary ADMs in a uni-directional direction (clockwise or counterclockwise) circled from a node 1 to another node 1 within the ring 3. In this case, the maximum number of channels required between ADMs within each ring system is equal to the total number of slots per fiber.
FIG. 15 is a schematic diagram illustrating an inter-ring connection network where plural bi-directional ring systems 81 to 83 are connected together. When a channel is set between different nodes 1 not belonging to the same ring 3, it must be routed via plural different bi-directional systems installed in different rings 3. For example, in the bi-directional ring systems 81 and 82 respectively installed in different rings 3, the cross connect unit (XC) 5 interconnects the ADMs 66 and 67 in the same node 14. The XC unit has the cross connect function of arbitrarily connecting a routing channel from a certain port to another port and the slot conversion function of converting the slot number allocated to the channel routing each port.
The ADM 68 belonging to the bi-directional ring system 82 is connected to the ADM 69 belonging to the bi-directional ring system 83. When the channel 105 is set between the ADM 65 installed to the node 13 and the ADM 68 installed to the node 15, the slot #1 is allocated to the route between the ADMs 65 and 66 belonging to the bi-directional ring system 81 while the slot #3 is allocated to the route between the ADMs 67 and 68 belonging to the bi-directional ring system 82.
In this case, the XC 5 switches the slot number #1 to the slot number #3. When the XC 5 performs the slot conversion by interconnecting different bi-directional ring systems 8, independent slot numbers can be allocated to bi-directional ring systems through which channels are routed. As a result, the improved channel accommodation efficiency can be expected, compared with the case of no connection with the XC 5. However, it should be noted that when the XC 5 in the node 14 is in a trouble state, the channel 105 cannot be recovered.
There is the conventional designing method, which decides the placement of ring systems and-path routes to minimize the facility costs of an inter-ring connection network or a network configured of plural ring systems, based on the numerical programming. Such a method is disclosed in the literature, S. Bortolon, H. M. F. Tavares, R. V. Riberio, E. Quaglia, and M. A. Bergamaschi, xe2x80x9cA methodology to SDH networks design using optimization toolsxe2x80x9d, Proceedings of IEEE Globcom 96, pp. 1867-1871, 1996.
In the above-mentioned prior art, a bundle of channels routing via the same node 1 or same span 2 to the same demand pair 11 (refer to FIG. 17) is here called a path. The capacity of a path corresponds to the total number of channels contained therein. A route candidate of a path is provided based on the span 1, the ring 3 or the node 2. The demand pair 11 represents a pair of nodes on the both ends of a path to be set. One or plural paths are set across the demand pair 11 to secure the number of channels (required capacity) required between the nodes.
According to the foregoing reference, the path accommodated in the bi-directional ring system 8 provides a route based on the span 2 and is called a span base path 41. As shown in FIG. 16, all span base paths 41, routing a certain span 2, are accommodated in all bi-directional ring systems 8 installed to a candidate ring 3 containing the span 2. Moreover, as shown in FIG. 17, the path accommodated in a uni-directional ring system 9 provides a route based on the ring 3 to which all uni-directional ring systems are installed. Such a path is here called a ring base path 42.
In order to formulate a design problem based on the above-mentioned concepts, the symbols are defined as follows:
R=1 to R (a number allocated to a ring)
S=1 to S (a number allocated to a span)
P=1 to P (a number allocated to a demand pair)
1p=1 to Lp (a number allocated to a path candidate used by a demand pair p)
FIG. 18 shows definitions of constants according to the items 1 to 7. FIG. 19 shows definitions of variables according to the items 1 to 3. The conventional inter-ring connection network design problem can be formulated by the following prescribed formula 1 using the above-listed definitions.
Problem 1:
(formula 1)                               minimize          ⁢                      xe2x80x83                    ⁢                                                    ∑                R                                            r                =                1                                      ⁢                                          a                r                B                            ⁢                              d                r                B                                                    +                                            ∑              R                                      r              =              1                                ⁢                                    a              r              U                        ⁢                          d              r              U                                                          (1-1)                                          subject          ⁢                      xe2x80x83                    ⁢          to          ⁢                      xe2x80x83                    ⁢                                                    ∑                Lp                                            lp                =                1                                      ⁢                          c              lp                                      =                              v            p                    ⁡                      (                                          p                =                1                            ,              …              ⁢                              xe2x80x83                            ,              P                        )                                              (1-2)                                                                    ∑              p                                      p              =              1                                ⁢                                                    ∑                Lp                                            lp                =                1                                      ⁢                                          g                lp                S                            ⁢                              c                lp                                                    ≤                  Ω          ⁢                                                    ∑                R                                            r                =                1                                      ⁢                                          g                r                S                            ⁢                                                d                  r                  B                                ⁡                                  (                                                            s                      =                      1                                        ,                    …                    ⁢                                          xe2x80x83                                        ,                    S                                    )                                                                                        (1-3)                                                                    ∑              P                                      p              =              1                                ⁢                                                    ∑                P                                            lp                =                1                                      ⁢                                          g                lp                r                            ⁢                              c                lp                                                    ≤                  Ω          ⁢                      xe2x80x83                    ⁢                                    d              r              U                        ⁡                          (                                                r                  =                  1                                ,                …                ⁢                                  xe2x80x83                                ,                R                            )                                                          (1-4)            
The formula (1-1) is an objective function to be minimized and represents the total costs required to install the bi-directional ring system 8 and the uni-directional ring system 9. The formula (1-2) is a constraint formula representing that the sum of capacities allocated to paths 4 usable across the demand pair 11 is equal to the capacity required across the demand pair 11.
The formula (1-3) is a constraint formula representing that the sum of capacities allocated to the span base path 41 routing each span 2 does not exceed the sum of capacities of the bi-directional ring systems 8 installed to a ring candidate 3 containing the span 2. The formula (1-4) is a constraint formula insuring that the sum of capacities allocated to the span base path 42 routing each span 2 does not exceed the sum of capacity of the uni-directional ring systems 9 installed to a ring candidate 3.
FIG. 20 shows a concrete design procedure in the conventional inter-ring connection network designing method. First, a route for a candidate ring 3 as well as a route for a candidate span base path 41 and a candidate ring base path 42 are decided based on connection information about the node 1 and the span 2 (step C1). Next, an integer programming problem 1 is created based on the decided results (step C2). Finally, the problem 1 is solved using the branch restricting method. The number of bi-directional ring systems 8 installed in a candidate ring 3, the number of uni-directional ring systems 9 installed in a candidate ring 3, the capacity allocated to each span base path 41, and the capacity allocated to each ring base path 42 are decided using the resultant solutions (step C3).
The branch restricting method is a typical method for solving the linear programming problem, as shown, for example, by H. P. Williams, xe2x80x9cMathematical Programming Modelxe2x80x9d, published by Sangyo-Tosyo. Here, a variable with no integer value is selected from solutions of a linear programming problem selected at a stage. Further, the next linear programming problem, obtained by adding a constraint formula restricting the range covered by the selected variable, is solved using integers larger or smaller than the value of the selected variable. This procedure is repeatedly applied to variables not being integers so that solutions in which all variables become integers are obtained.
However, the conventional network designing method has the following disadvantages.
The first problem is that design results cannot be reflected to the channel setting in an actual inter-ring connection network without any process. The resultant solutions are used to obtain routes for the span base path 41 and the ring base path 42, installation spots of the bi-directional ring system 8 and the uni-directional ring system 9, and the number of ring systems to be installed. It is impossible to specify the slot number allocated to each channel routing the each bi-directional ring system 8 as well as the number of channels to be routed between nodes 1. Moreover, the node 1 in which an ADM is installed cannot be specified to an installed ring system.
The second problem is that when the costs regarding XCs or ADMs cannot be ignored to the costs regarding the ring systems, it is often difficult to optimize the comprehensive facility costs containing the cost of XCs. The reason is that since the conventional method does not provide a route candidate specifying the hub 12, being the node 1 installed with XC, the XC installation costs cannot be calculated. Moreover, since the conventional method does not specify nodes to which an ADM is installed, to an installed ring system, the number of ADMs to be installed cannot be calculated.
The third problem is that when a failure occurs in a hub 12 to which the XC unit for connectting the ring systems is installed, it is impossible to recover the hub 12. The reason is that the conventional method does not incorporate the means of specifying the hub 12, being the node 1 to which XC is installed, and additionally securing a previously allocated capacity to a path subject to the failure.
The present invention is made to solve the above-mentioned problems.
The objective of the invention is to provide a network designing method that can immediately use available design results for the construction and operation of an actual network and to provide a recording medium that records the control program for the above-mentioned network designing method.
Another objective of the present invention is to provide a network designing method that can minimize the total setup costs containing costs regarding the cross connect (XC) and the add drop multiplexer (ADM) and to provide a recording medium that records the control program for the above-mentioned network designing method.
Still another objective of the present invention is to provide a network designing method that can satisfy a required capacity even in a hub failure state and to provide a recording medium that records the control program for the above-mentioned network designing method.
The objective of the present invention is achieved by a network designing method, comprising the steps of providing a route for each of path candidates installable between demand pairs by means of connection relationships between nodes and spans in a network, a demand pair being a terminal terminating node, and a hub being a node to which a cross connect unit is installable, based on ring candidates on which a bi-directional ring system or unidirectional ring system is installable and an arrangement of rings contained in the demand pair and the hub; creating an integer programming problem containing at least a first variable, a second variable, a third variable, a fourth variable, a fifth variable, a sixth variable, a seventh variable, a first constraint, a second constraint, a third constraint, a fourth constraint, and a fifth constraint; the first variable representing a capacity allocated to each of the paths; the second variable representing whether a k-th bidirectional ring system is installed to a r-th ring candidate; the third variable representing whether an add drop multiplexer is installed, wherein the add drop multiplexer branches and inserts the channel from said k-th bi-directional ring system which is installed to the r-th ring candidate, in the node contained in the r-th ring candidate; the fourth variable representing whether the channel, to which a slot number is allocated, is routed on clockwise route or counterclockwise route between respective adjacent nodes, the adjacent nodes being contained in the r-th ring candidate and in at least one of the path candidates to the demand pair in the k-th bi-directional ring system installed to the r-th ring candidate; the fifth variable representing whether said k-th uni-directional ring system is installed to the r-th ring candidate; the sixth variable representing whether add drop mulitplexer is installed, the add drop multiplexer branching and inserting the channel from the k-th unidirectional ring system installed to the r-th ring candidate in the node contained in the r-th ring candidate; the seventh variable representing the number of channels to be routed between respective adjacent nodes contained in the r-th ring candidate and in at least one of routes for the path candidates to the demand pair in the k-th uni-directional ring system installed to the r-th ring candidate; the first constraint representing that the total number of channels is smaller than the total number of capacities allocated to all paths routing the adjacent nodes, the channels routing the bi-directional systems and the unidirectional systems installed to each of the ring candidates containing the adjacent nodes in respective adjacent nodes existing on at least one of the routes for the path candidates; the second constraint representing that when the k-th bi-directional ring system is installed to the r-th ring candidate, the number of passable channels to which slots are allocated in respective spans contained in said r-th ring candidate is only one of all clockwise or counterclockwise routes routing the span, the routes existing in adjacent nodes contained in the r-th ring candidate or in at least one route of the path candidates to the demand pair; the third candidate representing that when the k-th uni-directional ring system is installed to the r-th ring candidate, the total number of channels routing between adjacent nodes contained in the r-th ring candidate and in at least one route of the path candidates to the demand pair does not exceed the total number of slots per fiber; the fourth constraint representing that when an add drop mulitplexer is installed to each of nodes contained in the r-th ring of the k-th bi-directional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed twice the total number of channels per fiber; the fifth constraint representing that when an ADM (add drop multiplexer) is installed to each of nodes contained in the r-th ring of the k-th unidirectional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed the total number of channels per fiber; and deciding the number of the bi-directional ring systems to be installed to the ring candidate based on a solution of the integer programming problem, the number of the uni-directional ring systems to be set to the ring candidate based on a solution of the integer programming problem, a node to which the ADM is installed in each bi-directional ring system, and a slot number allocated to a channel routing the bi- and uni-directional ring systems to be installed.
According to the present invention, a network designing method, comprises the steps of providing a route for each of path candidates installable between demand pairs by means of connection relationships between nodes and spans in a network, a demand pair being a terminal terminating node, and a hub being a node to which a cross connect unit is installable, based on ring candidates on which a bidirectional ring system is installable and an arrangement of rings contained in the demand pair and the hub; creating an integer programming problem containing at least a first variable, a second variable, a third variable, a fourth variable, a first constraint, a second constraint, and a third constraint; the first variable representing a capacity allocated to each of paths; the second variable representing whether a k-th bi-directional ring system is installed to a r-th ring candidate; the third variable representing whether an add drop multiplexer is installed, wherein the add drop multiplexer branches and inserts the channel from said k-th bidirectional ring system which is installed to the r-th ring candidate, in the node contained in the r-th ring candidate; the fourth variable representing whether the channel, to which a slot number is allocated, is routed on clockwise route or counterclockwise route between respective adjacent nodes, the adjacent nodes being contained in the r-th ring candidate and in at least one of the path candidates to the demand pair in the k-th bidirectional ring system installed to the r-th ring candidate; the first constraint representing that the total number of channels is smaller than the total number of capacities allocated to all paths routing the adjacent nodes, the channels routing the bi-directional systems and the unidirectional systems installed to each of said ring candidates containing said adjacent nodes in respective adjacent nodes existing on at least one of routes for the path candidates; the second constraint representing that when the k-th bidirectional ring system is installed to the r-th ring candidate, the number of passable channels to which slots are allocated in respective spans contained in the r-th ring candidate is only one of all clockwise or counterclockwise routes routing the span, the routes existing in adjacent nodes contained in the ring candidate or in at least one route of the path candidates to the demand pair; the third constraint representing that when an add drop multiplexer is installed to each of nodes contained in the r-th ring of the k-th bi-directional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed twice the total number of channels per fiber; and deciding at least the number of the bi-directional ring systems to be installed to the ring candidate based on a solution of the integer programming problem, a node to which the add drop multiplexer is installed in the bi-directional ring system, and a slot number allocated to a channel routing the bi-directional ring system to be installed.
Moreover, according to the present invention, in a recording medium on which a program is recorded for executing a network designing method by a computer, the program comprises the steps of providing a route for each of path candidates installable between demand pairs by means of connection relationships between nodes and spans in a network, a demand pair being a terminal terminating node, and a hub being a node to which a cross connect unit is installable, based on ring candidates on which a bi-directional ring system or unidirectional ring system is installable and an arrangement of rings contained in the demand pair and the hub; creating an integer programming problem containing at least a first variable, a second variable, a third variable, a fourth variable, a fifth variable, a sixth variable, a seventh variable, a first constraint, a second constraint, a third constraint, a fourth constraint, and a fifth constraint; the first variable representing a capacity allocated to each of the paths; the second variable representing whether a k-th bi-directional ring system is installed to a r-th ring candidate; the third variable representing whether an add drop multiplexer is installed, wherein the add drop multiplexer branches and inserts the channel from said k-th bi-directional ring system which is installed to the r-th ring candidate, in the node contained in the r-th ring candidate; the fourth variable representing whether the channel, to which a slot number is allocated, is routed on clockwise route or counterclockwise route between respective adjacent nodes, the adjacent nodes being contained in the r-th ring candidate and in at least one of the path candidates to the demand pair in the k-th bi-directional ring system installed to the r-th ring candidate; the fifth variable representing whether said k-th uni-directional ring system is installed to the r-th ring candidate; the sixth variable representing whether add drop mulitplexer is installed, the add drop multiplexer branching and inserting the channel from the k-th unidirectional ring system installed to the r-th ring candidate in the node contained in the r-th ring candidate; the seventh variable representing the number of channels to be routed between respective adjacent nodes contained in the r-th ring candidate and in at least one of routes for the path candidates to the demand pair in the k-th unidirectional ring system installed to the r-th ring candidate; the first constraint representing that the total number of channels is smaller than the total number of capacities allocated to all paths routing the adjacent nodes, the channels routing the bidirectional systems and the uni-directional systems installed to each of the ring candidates containing the adjacent nodes in respective adjacent nodes existing on at least one of the routes for the path candidates; the second constraint representing that when the k-th bi-directional ring system is installed to the r-th ring candidate, the number of passable channels to which slots are allocated in respective spans contained in said r-th ring candidate is only one of all clockwise or counterclockwise routes routing the span, the routes existing in adjacent nodes contained in the r-th ring candidate or in at least one route of the path candidates to the demand pair; the third candidate representing that when the k-th uni-directional ring system is installed to the r-th ring candidate, the total number of channels routing between adjacent nodes contained in the r-th ring candidate and in at least one route of the path candidates to the demand pair does not exceed the total number of slots per fiber; the fourth constraint representing that when an add drop mulitplexer is installed to each of nodes contained in the r-th ring of the k-th bi-directional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed twice the total number of channels per fiber; the fifth constraint representing that when an ADM (add drop multiplexer) is installed to each of nodes contained in the r-th ring of the k-th unidirectional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed the total number of channels per fiber; and deciding the number of the bi-directional ring systems to be installed to the ring candidate based on a solution of the integer programming problem, the number of the unidirectional ring systems to be set to the ring candidate based on a solution of the integer programming problem, a node to which the ADM is installed in each bi-directional ring system, and a slot number allocated to a channel routing the bi- and uni-directional ring systems to be installed.
Furthermore, according to the present invention, in a recording medium on which a program is recorded for executing a network designing method by a computer, the program comprises the steps of providing a route for each of path candidates installable between demand pairs by means of connection relationships between nodes and spans in a network, a demand pair being a terminal terminating node, and a hub being a node to which a cross connect unit is installable, based on ring candidates on which a bi-directional ring system is installable and an arrangement of rings contained in the demand pair and the hub; creating an integer programming problem containing at least a first variable, a second variable, a third variable, a fourth variable, a first constraint, a second constraint, and a third constraint; the first variable representing a capacity allocated-to each of paths; the second variable representing whether a k-th bi-directional ring system is installed to a r-th ring candidate; the third variable representing whether an add drop multiplexer is installed, wherein the add drop multiplexer branches and inserts the channel from the k-th bi-directional ring system which is installed to the r-th ring candidate, in the node contained in the r-th ring candidate; the fourth variable representing whether the channel, to which a slot number is allocated, is routed on clockwise route or counterclockwise route between respective adjacent nodes, the adjacent nodes being contained in the r-th ring candidate and in at least one of the path candidates to the demand pair in the k-th bi-directional ring system installed to the r-th ring candidate; the first constraint representing that the total number of channels is smaller than the total number of capacities allocated to all paths routing the adjacent nodes, the channels routing the bi-directional systems and the unidirectional systems installed to each of the ring candidates containing the adjacent nodes in respective adjacent nodes existing on at least one of routes for the path candidates; the second constraint representing that when the k-th bi-directional ring system is installed to the r-th ring candidate, the number of passable channels to which slots are allocated in respective spans contained in the r-th ring candidate is only one of all clockwise or counterclockwise routes routing the span, the routes existing in adjacent nodes contained in the ring candidate or in at least one route of the path candidates to the demand pair; the third constraint representing that when an add drop multiplexer is installed to each of nodes contained in the r-th ring of the k-th bidirectional ring system installed to the r-th ring candidate, the total number of channels to be branched and inserted in each node does not exceed twice the total number of channels per fiber; and deciding at least the number of the bi-directional ring systems to be installed to the ring candidate based on a solution of the integer programming problem, a node to which the add drop multiplexer is installed in the bi-directional ring system, and a slot number allocated to a channel routing the bi-directional ring system to be installed.
In the above description, the adjacent node represents a pair of nodes being adjacent to each other in a candidate route for a node base path 43, as shown in FIG. 9, which is formed in the order of the node number belonging to the demand pair 11, the node number of the hub 12, the node number of the hub 12, node number of the hub 12, . . . , and another node number belonging to the demand pair 11. Let us now consider that the channel passing through adjacent nodes on the route for a node base path 43 routes within all bi-directional ring systems 8 or uni-directional ring systems 9 which may be installed to a candidate ring 3 containing the adjacent nodes.
Variables regarding a slot to be allocated to a clockwise or counterclockwise route between nodes 1 are set to channels routing a bi-directional ring system 8 to be installed to each candidate ring 3. The slot allocation can be decided to the channel which routes a bi-directional ring system 8 to be immediately installed, by means of the solution of the integer programming solved based on variables.
As shown in FIG. 9, a candidate route for the path 4 installable between the demand pair 11 is provided based on the arrangement of the nodes 1 being the demand pair 11 and the nodes 1 being the hubs 12. Thus, the sum of capacities of the path 4 routing the hubs 12 where the XC 5 are installed can be calculated. Hence, the costs regarding XZs 5 can be calculated from the number of XC units 5 installed at a hub 12. The resultant costs are included in the objective function so that the comprehensive facility costs can be minimized.
When a failed hub 12 adversely affects the node base path 43 included on the same route, the path allocation capacity becomes 0. At this time, the required capacity of the demand pair 11 is satisfied by the capacity allocated to another node base path 43, not affected by the failure. Hence, a capacity larger than the required capacity of each demand pair in a normal state is previously allocated to the node base path 43 on which the demand pair 11 is usable.